0/1 背包問題&分數背包問題都是...

在有限的背包容量下如何選擇物品使得總價值最大的問題～

但

• 0/1 背包問題：每個物品只能選擇一次，要麼選擇放入背包，要麼不選擇。這是一個布爾（二進制）決策問題～
  如果有三個物品，分別重量為 [10, 20, 30]，價值為 [60, 100, 120]，背包容量為 50，那麼每個物品只能選擇一次，要麼選擇放入背包，要麼不選擇。

• 分數背包問題：可以部分選取物品，也就是可以選擇物品的一部分放入背包。這是一個連續的決策問題，可以選擇物品的一部分來放入背包～
  如果有三個物品，分別重量為 [10, 20, 30]，價值為 [60, 100, 120]，背包容量為 50，那麼可以選擇部分物品的一部分來放入背包，例如可以選擇 30% 的第一個物品，60% 的第二個物品，等等。

總的來說分數背包問題的求解方法相對簡單，因為可以根據價值重量比率來選擇物品，而 0/1 背包問題需要使用動態規劃等方法來解決較複雜

貪心算法和動態規劃在解決優化問題時的策略和思路有著明顯的差別

• 貪心算法：
  局部最優策略：貪心算法在每一步都選擇當前情況下的最佳選擇，而不考慮全局最優解決方案。
  沒有回退：貪心算法做出的每一個決策都是最終解決方案的一部分，並且一旦做出了選擇，就不會回退。
  適用場景：貪心算法通常適用於問題具有「最優子結構」性質的情況，即全局最優解可以通過局部最優解組合得到～

• 動態規劃：
  保存子問題的解：動態規劃將問題分解成子問題並保存子問題的解決方案，以避免重複計算。
  全局最優解：動態規劃通過組合子問題的解決方案，最終得到全局最優解決方案。
  適用場景：動態規劃通常適用於問題具有「重疊子問題」性質的情況，即問題的解可以通過子問題的解組合得到解～

白話來說由於貪心算法在每一步僅僅考慮當前的最優選擇，而無法預測這種局部最優策略是否能夠導致全局最優解～
貪心算法通常更為簡單且容易實現，但可能不能保證獲得全局最優解；而動態規劃需要更多的計算和存儲空間，但能夠保證獲得全局最優解。因此，在解決具體問題時，需要根據問題的特點選擇合適的算法。

找零問題（Coin Change Problem）

在某些問題中，如果問題具有「最優子結構」性質，則可以使用貪心算法來獲得一個近似最優解，並且貪心算法的運行速度通常較快。
然而，在其他情況下，如某些動態規劃問題，可能需要耗費更多計算資源，但能夠確保獲得全局最優解。

# 使用貪心算法解決找零錢問題
def greedy_coin_change(coins, amount):
    coins.sort(reverse=True)
    num_coins = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            num_coins += 1
    return num_coins

# 使用動態規劃解決找零錢問題
def dp_coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# 測試示例
coins = [1, 5, 10, 25]
amount = 17

# 使用貪心算法
greedy_result = greedy_coin_change(coins, amount)
print(f"貪心算法得到的最少硬幣數量為：{greedy_result}")

# 使用動態規劃
dp_result = dp_coin_change(coins, amount)
print(f"動態規劃得到的最少硬幣數量為：{dp_result}")

這個示例中，coins 是可用的硬幣面額列表，amount 是要湊成的金額。greedy_coin_change 使用了貪心算法，而 dp_coin_change 使用了動態規劃。你可以嘗試不同的 coins 和 amount 值來看看它們的不同表現～